#include "MLMovStream.h"
#include "MLClustering_KMeans.h"
#include "MLTools_Stat.h"
#include "MLGlobals.h"
using namespace mylablib;

///////////////////////////////////////////////////////////////////////////
// CMLMovStreamCluster
CMLMovStreamCluster::CMLMovStreamCluster(CMLMovStream *pClustering, int nID)
{
	m_pClustering  = pClustering;
	m_pDistFunc = pClustering->GetDistanceFunc();
	m_vLS.zero();
	m_vSS.zero();
	m_nID = nID;
}

CMLMovStreamCluster::~CMLMovStreamCluster(void)
{
}

int CMLMovStreamCluster::Create(const CMLDataSet& dataSet)
{
	int i;
	if (dataSet.IsEmpty())
	{
		ML_ASSERT(false);
		return -1;
	}

	// Calculate the security radius and average movement
	SlideWindowElem_ elem;
	m_SlideWindow.clear();
	m_vLS.zero();
	m_vSS.zero();
	int dataSize = dataSet.Count();
	for (i=0; i<dataSize; i++)
	{
		const CMLDataPoint& dataPoint = dataSet.Get(i);
		m_vLS.add(dataPoint);
		m_vSS.add(dataPoint^2);
		// Push into the slide window
		elem.dataPoint = dataSet.Get(i);
		elem.nTime = m_pClustering->GetCurTimeCounter();
		m_SlideWindow.push_back(elem);
	}
	m_dOriginRadius = GetRadius();
	m_OriginCenter = GetCenter();
	
	return 0;
}

int CMLMovStreamCluster::Absorb(const CMLDataPoint &dataPoint, int nTime)
{
	// Push the new data point and movement
	SlideWindowElem_ newElem;
	newElem.dataPoint  = dataPoint;
	newElem.nTime  = nTime;
	m_vLS.add(newElem.dataPoint);
	m_vSS.add(newElem.dataPoint^2);

	// Push the new element
	m_SlideWindow.push_back(newElem);
	return 0;
}

int CMLMovStreamCluster::Popout(int nTimeDeadline)
{
	while(m_SlideWindow.size() > 0)
	{
		const SlideWindowElem_& frontElem = m_SlideWindow.front();
		if (frontElem.nTime < nTimeDeadline)
		{
			m_vLS.sub(frontElem.dataPoint);
			m_vSS.sub(frontElem.dataPoint^2);
			// Pop out
			m_SlideWindow.pop_front();
		}
		else
		{
			break;
		}
	}
	return 0;
}

int CMLMovStreamCluster::Reset(void)
{
	m_dOriginRadius = GetRadius();
	m_OriginCenter = GetCenter();
	return 0;
}

bool CMLMovStreamCluster::TriggerDriftEvent(void)
{
	if (m_pClustering->GetMaxDriftFactor() < 0)
		return false;

	double dCenterDrift = m_pDistFunc->Distance(GetCenter(), m_OriginCenter);
	if (dCenterDrift > m_dOriginRadius * m_pClustering->GetMaxDriftFactor())
		return true;
	else
		return false;
}

bool CMLMovStreamCluster::TriggerExpandEvent(void)
{
	if (m_pClustering->GetStretchFactor() < 0)
		return false;

	if (GetRadius() > m_dOriginRadius * m_pClustering->GetStretchFactor() && m_SlideWindow.size() > 2)
		return true;
	else
		return false;
}

bool CMLMovStreamCluster::TriggerShrinkEvent(void)
{
	if (m_pClustering->GetStretchFactor() < 0)
		return false;

	if (GetRadius() < (m_dOriginRadius / m_pClustering->GetStretchFactor()) && m_SlideWindow.size() > 2)
		return true;
	else
		return false;
}

bool CMLMovStreamCluster::TriggerDieOutEvent(void)
{	
	if (GetSWLength() < 2)
		return true;
	
	if (m_pClustering->GetMinDataPointNumberRatio() >= 0)
	{
		if (GetSWLength() < m_pClustering->GetTotalSWLength() * m_pClustering->GetMinDataPointNumberRatio())
			return true;
	}

	/*if (m_pClustering->GetMaxAge() >= 0)
	{
		if (m_pClustering->GetCurTimeCounter() - GetAvgTimeStamp(m_pClustering->GetNumLastTimeStampCheck()) > m_pClustering->GetMaxAge())
			return true;
	}*/

	return false;
}

bool CMLMovStreamCluster::TriggerSplitEvent(void)
{
	if (m_pClustering->GetMaxRadius() < 0)
		return false;

	return GetRadius() > m_pClustering->GetMaxRadius();
}

bool CMLMovStreamCluster::TriggerMergeEvent(CMLMovStreamCluster* pNearCluster)
{
	double dCenterDrift = m_pDistFunc->Distance(GetCenter(), pNearCluster->GetCenter());
	double dSecurityCenterDist = (GetRadius() + pNearCluster->GetRadius()) * m_pClustering->GetMergeFactor();
	return dCenterDrift < dSecurityCenterDist;
}

int CMLMovStreamCluster::ExecuteMove(void)
{
	m_OriginCenter = GetCenter();
	m_dOriginRadius = GetRadius();
	return 0;
}

int CMLMovStreamCluster::ExecuteSplit(CMLMovStreamCluster* pNewCluster)
{
	CMLDataPoint center = GetCenter();

	// Find the farest data point
	double dMaxDist = 0.0;
	CMLDataPoint FarestPoint;
	std::list<SlideWindowElem_>::const_iterator Iter;
	std::list<SlideWindowElem_>::const_iterator PreIter;
	for (Iter=m_SlideWindow.begin(); Iter!=m_SlideWindow.end(); Iter++)
	{
		double dDist = m_pDistFunc->Distance(center, (*Iter).dataPoint);
		if (dDist > dMaxDist)
		{
			dMaxDist = dDist;
			FarestPoint = (*Iter).dataPoint;
		}
	}

	// Split the dataset
	Iter=m_SlideWindow.begin();
	while(Iter != m_SlideWindow.end())
	{
		const CMLDataPoint& dataPoint = (*Iter).dataPoint;
		double dDist1 = m_pDistFunc->Distance(dataPoint, FarestPoint);
		double dDist2 = m_pDistFunc->Distance(dataPoint, center);
		if (dDist1 < dDist2)
		{
			CMLDataPoint squareDataPoint = dataPoint^2;
			pNewCluster->m_vLS.add(dataPoint);
			pNewCluster->m_vSS.add(squareDataPoint);
			this->m_vLS.sub(dataPoint);
			this->m_vSS.sub(squareDataPoint);

			pNewCluster->m_SlideWindow.push_back(*Iter);
			PreIter = Iter;
			Iter++;
			m_SlideWindow.erase(PreIter);
		}
		else
		{
			Iter++;
		}
	}

	pNewCluster->Reset();
	this->Reset();

	return 0;
}

int CMLMovStreamCluster::ExecuteThrowOut(void)
{
	// Split throw part
	CMLMovStreamCluster* pThrowPart = new CMLMovStreamCluster(m_pClustering, -1);
	ExecuteSplit(pThrowPart);

	// Die-out the throw part
	pThrowPart->ExecuteDieOut();

	delete pThrowPart;
	return 0;
}

int CMLMovStreamCluster::ExecuteStretch(void)
{
	m_dOriginRadius = GetRadius();
	return 0;
}

int CMLMovStreamCluster::ExecuteDieOut(void)
{
	int i;
	std::list<SlideWindowElem_>::const_iterator Iter;
	std::vector<CMLDataPoint> vCenters;
	
	// Get all other centers of clusters
	vCenters.resize(m_pClustering->GetMicroClusters().size());
	for (i=0; i<(int)m_pClustering->GetMicroClusters().size(); i++)
	{
		CMLMovStreamCluster* pOtherCluster = m_pClustering->GetMicroClusters()[i];
		if (pOtherCluster == NULL)
			continue;
		if (this == pOtherCluster)
			continue;
		vCenters[i] = pOtherCluster->GetCenter();
	}
	// Redistribute data points to other clusters
	for(Iter=m_SlideWindow.begin(); Iter!=m_SlideWindow.end(); Iter++)
	{
		double dMinDist = DBL_MAX;
		CMLMovStreamCluster* pNearestCluster = NULL;
		for (i=0; i<(int)m_pClustering->GetMicroClusters().size(); i++)
		{
			CMLMovStreamCluster* pOtherCluster = m_pClustering->GetMicroClusters()[i];
			if (pOtherCluster == NULL)
				continue;
			if (this == pOtherCluster)
				continue;
			double dDist = m_pDistFunc->Distance((*Iter).dataPoint, vCenters[i]);
			if (dDist < dMinDist)
			{
				pNearestCluster = pOtherCluster;
				dMinDist = dDist;
			}
		}
		// Absorb
		pNearestCluster->Absorb((*Iter).dataPoint, (*Iter).nTime);
	}

	return 0;
}

int CMLMovStreamCluster::ExecuteMerge(CMLMovStreamCluster *pNearCluster)
{
	std::list<SlideWindowElem_>::const_iterator Iter = pNearCluster->m_SlideWindow.begin();
	for (; Iter != pNearCluster->m_SlideWindow.end(); Iter++)
	{
		Absorb((*Iter).dataPoint, (*Iter).nTime);
	}
	Reset();
	return 0;
}


///////////////////////////////////////////////////////////////////////////
// CMLMovStream
CMLMovStream::CMLMovStream(void)
{
	m_pDistFunc = mlglobals.GetEuclideanDistance();
	m_nInitNumber = 16;
	m_nNumInitClusters = 4;
	m_nDataPointTotalNumber = 0;
	m_dMaxRadius = 1.0;
	m_dMaxDriftFactor = 1.0;
	m_dStretchFactor = 0.5;
	m_dMaxAge = 16.0;
	m_dMergeFactor = 1.0;
	m_dMinDataPointNumberRatio = 0.1;
	m_nTimeCounter = 0;
	m_nClusterIdCounter = 0;
}

CMLMovStream::~CMLMovStream(void)
{
	Release();
}

int CMLMovStream::Release(void)
{
	int i;
	for (i=0; i<(int)m_vpMicroClusters.size(); i++)
	{
		if (m_vpMicroClusters[i] != NULL)
		{
			delete m_vpMicroClusters[i];
			m_vpMicroClusters[i] = NULL;
		}
	}
	m_vpMicroClusters.clear();
	return 0;
}

int CMLMovStream::SetParameters(const std::wstring& wstrParams)
{
	return 0;
}

int CMLMovStream::Insert(const CMLDataPoint& dataPoint)
{
	int i;
	int nRet;
	if (m_nDataPointTotalNumber < m_nInitNumber)
	{
		m_DataSet.Insert(dataPoint);
		if (m_nDataPointTotalNumber == m_nInitNumber -1)
		{
			m_nTimeCounter = m_nInitNumber;
			// Start to create the Tree
			nRet = CreateClusters();
			// Empty dataset
			m_DataSet.Clear();
		}
		else
		{
			nRet = 0;
		}
	}
	else
	{
		// Find the nearest cluster
		int nNearestClusterIndex = FindNearestCluster(dataPoint);
		if (nNearestClusterIndex == -1)
		{
			m_DataSet.Insert(dataPoint);
			if (m_DataSet.Count() >= m_nInitNumber * m_dMinDataPointNumberRatio * m_nNumInitClusters)
			{
				GrowNewCluster();
				// Empty dataset
				m_DataSet.Clear();
			}
		}
		else
		{
			// Cluster Absorb
			CMLMovStreamCluster* pCluster = m_vpMicroClusters[nNearestClusterIndex];
			pCluster->Absorb(dataPoint, m_nTimeCounter);
			// Pop out outdated data point
			for (i=0; i<(int)m_vpMicroClusters.size(); i++)
				m_vpMicroClusters[i]->Popout(m_nTimeCounter - m_nTotalSWLength);
		}
		m_nTimeCounter++;
		nRet = 0;
	}
	m_nDataPointTotalNumber++;
	return nRet;
}

int CMLMovStream::GetClusters(const std::wstring& params, std::vector<CMLDataCluster>& vClusters)
{
	int i;

	// Check before get cluster
	std::vector<CMLMovStreamClusterEvent> vEvents;
	CheckClustersEvents(vEvents);
	
	int nNumClusters = GetNumClusters();
	vClusters.resize(nNumClusters);
	
	for(i=0; i<nNumClusters; i++)
	{
		CMLMovStreamCluster* pCluster = m_vpMicroClusters[i];
		vClusters[i].center = pCluster->GetCenter();
	}
	return 0;
}

int CMLMovStream::CreateClusters(void)
{
	int i;
	CMLClustering_KMeans kMeans;
	int nK = m_nNumInitClusters;
	
	// Initialize the k-means clustering method
	kMeans.SetDistanceFunc(GetDistanceFunc());
	kMeans.SetK(nK);

	// Use K-Means to create micro-clusters
	std::vector<CMLDataCluster> vClusters;
	int nRet = kMeans.DoClustering(m_DataSet, vClusters);
	if (ML_FAILED(nRet))
		return nRet;

	// Create the micro-clusters
	m_vpMicroClusters.clear();
	m_vpMicroClusters.resize((size_t)nK);
	double dAvgRadius = 0;
	for (i=0; i<nK; i++)
	{
		m_vpMicroClusters[i] = new CMLMovStreamCluster(this, m_nClusterIdCounter++);
		m_vpMicroClusters[i]->Create(vClusters[i].dataset);
		dAvgRadius += m_vpMicroClusters[i]->GetRadius();
	}

	return 0;
}

int CMLMovStream::FindNearestCluster(const CMLDataPoint& point)
{
	if (m_vpMicroClusters.size() == 0)
		return -1;

	double dMinDist = DBL_MAX;
	int nNearestIndex = -1;
	// Find the minimum distance child node
	int i;
	for (i=0; i<(int)m_vpMicroClusters.size(); i++)
	{
		CMLMovStreamCluster* pCluster = m_vpMicroClusters[i];
		double dDist = m_pDistFunc->Distance(point, pCluster->GetCenter());
		if (dDist < dMinDist)
		{
			nNearestIndex = i;
			dMinDist = dDist;
		}
	}
	
	return nNearestIndex;
}

int CMLMovStream::GrowNewCluster(void)
{
	CMLMovStreamCluster* pCluster = new CMLMovStreamCluster(this, m_nClusterIdCounter++);
	pCluster->Create(m_DataSet);
	m_vpMicroClusters.push_back(pCluster);
	return 0;
}

int CMLMovStream::CheckClustersEvents(std::vector<CMLMovStreamClusterEvent>& vEvents)
{
	int nRet = 0;
	int nClusterIndex;
	int j;

	vEvents.clear();
	CMLMovStreamClusterEvent newEvent;
	int nNumClusters = (int)m_vpMicroClusters.size();

	std::vector<CMLMovStreamCluster*> vpNewClusters;
	for (nClusterIndex=0; nClusterIndex<(int)m_vpMicroClusters.size(); nClusterIndex++)
	{
		CMLMovStreamCluster* pCluster = m_vpMicroClusters[nClusterIndex];
		if (pCluster == NULL)
			continue;
		if (pCluster->TriggerDriftEvent())
		{
			nRet = pCluster->ExecuteMove();
			ML_ON_FAILED_RETURN(nRet);
			// Add new event
			newEvent.nCluster = nClusterIndex;
			newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_Drift;
			vEvents.push_back(newEvent);
			// Check the merge trigger
			/*if (nNumClusters > m_nNumMinClusters)
			{*/
				for (j=0; j<(int)m_vpMicroClusters.size(); j++)
				{
					CMLMovStreamCluster* pNearCluster = m_vpMicroClusters[j];
					if (pNearCluster == NULL)
						continue;
					if (pCluster == pNearCluster)
						continue;
					if (pCluster->TriggerMergeEvent(pNearCluster))
					{
						nRet = pCluster->ExecuteMerge(pNearCluster);
						ML_ON_FAILED_RETURN(nRet);
						delete pNearCluster;
						m_vpMicroClusters[j] = NULL;
						// Add new event
						newEvent.nCluster  = nClusterIndex;
						newEvent.nCluster2 = j;
						newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_Merge;
						vEvents.push_back(newEvent);
						nNumClusters--;
					}
				}
			/*}*/
		}

		if (pCluster->TriggerShrinkEvent())
		{
			nRet = pCluster->ExecuteStretch();
			ML_ON_FAILED_RETURN(nRet);
			// Add new event
			newEvent.nCluster = nClusterIndex;
			newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_Shrink;
			vEvents.push_back(newEvent);
		}

		if (pCluster->TriggerExpandEvent())
		{
			nRet = pCluster->ExecuteStretch();
			ML_ON_FAILED_RETURN(nRet);
			// Add new event
			newEvent.nCluster = nClusterIndex;
			newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_Expand;
			vEvents.push_back(newEvent);
			// Check larger than max radius
			if (pCluster->TriggerSplitEvent())
			{
				if (nNumClusters == m_nNumMaxClusters)
				{
					nRet = pCluster->ExecuteThrowOut();
					ML_ON_FAILED_RETURN(nRet);
					// Add new event
					newEvent.nCluster = nClusterIndex;
					newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_ThrowOut;
					vEvents.push_back(newEvent);
				}
				else
				{
					CMLMovStreamCluster* pNewCluster = new CMLMovStreamCluster(this, m_nClusterIdCounter++);
					nRet = pCluster->ExecuteSplit(pNewCluster);
					ML_ON_FAILED_RETURN(nRet);

					//if (pNewCluster->TriggerDieOutEvent())
					//{
					//	nRet = pNewCluster->ExecuteDieOut();
					//	ML_ON_FAILED_RETURN(nRet);
					//	delete pNewCluster;
					//	pNewCluster = NULL;
					//}
					//else
					//{
						vpNewClusters.push_back(pNewCluster);
						// Add new event
						newEvent.nCluster = nClusterIndex;
						newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_Split;
						vEvents.push_back(newEvent);
						nNumClusters++;
					//}
				}
			}

			/*if (nNumClusters > m_nNumMinClusters)
			{*/
				// Check the merge trigger
				for (j=0; j<(int)m_vpMicroClusters.size(); j++)
				{
					CMLMovStreamCluster* pNearCluster = m_vpMicroClusters[j];
					if (pNearCluster == NULL)
						continue;
					if (pCluster == pNearCluster)
						continue;
					if (pCluster->TriggerMergeEvent(pNearCluster))
					{
						nRet = pCluster->ExecuteMerge(pNearCluster);
						ML_ON_FAILED_RETURN(nRet);
						delete pNearCluster;
						m_vpMicroClusters[j] = NULL;
						// Add new event
						newEvent.nCluster  = nClusterIndex;
						newEvent.nCluster2 = j;
						newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_Merge;
						vEvents.push_back(newEvent);
						nNumClusters--;
						j--;
					}
				}
			/*}*/
		}

		if (pCluster->TriggerDieOutEvent())
		{
			nRet = pCluster->ExecuteDieOut();
			ML_ON_FAILED_RETURN(nRet);

			delete pCluster;
			m_vpMicroClusters[nClusterIndex] = NULL;
			// Add new event
			newEvent.nCluster = nClusterIndex;
			newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_DieOut;
			vEvents.push_back(newEvent);

			nNumClusters--;
		}
	}

	for (nClusterIndex=0; nClusterIndex<(int)m_vpMicroClusters.size(); nClusterIndex++)
	{
		if (m_vpMicroClusters[nClusterIndex] == NULL)
		{
			m_vpMicroClusters.erase(m_vpMicroClusters.begin() + nClusterIndex);
			nClusterIndex--;
		}
	}

	for(nClusterIndex=0; nClusterIndex<(int)vpNewClusters.size(); nClusterIndex++)
	{
		m_vpMicroClusters.push_back(vpNewClusters[nClusterIndex]);
	}

	// Check the minimal number of clusters
	while ((int)m_vpMicroClusters.size() < m_nNumMinClusters)
	{
		double dMaxRadius = 0;
		int nMaxRIndex = -1;
		// Find the max radius cluster
		for (nClusterIndex=0; nClusterIndex<(int)m_vpMicroClusters.size(); nClusterIndex++)
		{
			if (dMaxRadius < m_vpMicroClusters[nClusterIndex]->GetRadius())
			{
				dMaxRadius = m_vpMicroClusters[nClusterIndex]->GetRadius();
				nMaxRIndex = nClusterIndex;
			}
		}

		// Split the largest cluster
		if (nMaxRIndex != -1)
		{
			CMLMovStreamCluster* pCluster = m_vpMicroClusters[nMaxRIndex];
			CMLMovStreamCluster* pNewCluster = new CMLMovStreamCluster(this, m_nClusterIdCounter++);
			nRet = pCluster->ExecuteSplit(pNewCluster);
			ML_ON_FAILED_RETURN(nRet);

			//if (pNewCluster->TriggerDieOutEvent())
			//{
			//	nRet = pNewCluster->ExecuteDieOut();
			//	ML_ON_FAILED_RETURN(nRet);
			//	delete pNewCluster;
			//	pNewCluster = NULL;
			//}
			//else
			//{
				m_vpMicroClusters.push_back(pNewCluster);
				// Add new event
				newEvent.nCluster = nClusterIndex;
				newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_Split;
				vEvents.push_back(newEvent);
			//}
		}
		else
		{
			break;
		}
	}

	// Check maximal number of clusters
	while ((int)m_vpMicroClusters.size() > m_nNumMaxClusters)
	{
		double dMinDist = DBL_MAX;
		int nMergeClusterIndex1 = -1;
		int nMergeClusterIndex2 = -1;
		// Find the max radius cluster
		for (nClusterIndex=0; nClusterIndex<(int)m_vpMicroClusters.size(); nClusterIndex++)
		{
			CMLDataPoint center = m_vpMicroClusters[nClusterIndex]->GetCenter();
			for (j=nClusterIndex+1; j<(int)m_vpMicroClusters.size(); j++)
			{
				double dDist = m_pDistFunc->Distance(center, m_vpMicroClusters[j]->GetCenter());
				if (dDist < dMinDist)
				{
					nMergeClusterIndex1 = nClusterIndex;
					nMergeClusterIndex2 = j;
					dDist = dMinDist;
				}
			}
		}

		// Merge the two closest clusters
		if (nMergeClusterIndex1 != -1 && nMergeClusterIndex2 != -1)
		{
			CMLMovStreamCluster* pCluster = m_vpMicroClusters[nMergeClusterIndex1];
			CMLMovStreamCluster* pNearCluster = m_vpMicroClusters[nMergeClusterIndex2];
			nRet = pCluster->ExecuteMerge(pNearCluster);
			ML_ON_FAILED_RETURN(nRet);
			delete pNearCluster;
			m_vpMicroClusters.erase(m_vpMicroClusters.begin() +nMergeClusterIndex2);
			// Add new event
			newEvent.nCluster  = nMergeClusterIndex1;
			newEvent.nCluster2 = nMergeClusterIndex2;
			newEvent.nEvent = CMLMovStreamClusterEvent::ClusterEvent_Merge;
			vEvents.push_back(newEvent);
		}
		else
		{
			break;
		}
	}


	return 0;
}

